#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>


typedef int ElemType;
// 定义一个动态数组
typedef struct SSTable {
    ElemType *elem;
    int length;
};

// 数组初始化
void ST_Init(SSTable &ST, int length) {
    ST.length = length;
    ST.elem = (ElemType*) malloc(sizeof (ElemType)*length);
    // 生成一个随机序列
    srand(time(NULL));  // 初始化随机种子，使得后面的rand()函数生成随机数
    for (int i = 0; i < ST.length; ++i) {
        ST.elem[i] = rand()%100;
    }
}

// 数组打印
void ST_Print(SSTable ST) {
    for (int i = 0; i < ST.length; ++i) {
        printf("%3d", ST.elem[i]);
    }
    printf("\n");
}

// 数组交换元素顺序
void swap(ElemType &a, ElemType &b) {
    ElemType tmp = a;
    a = b;
    b = tmp;
}

/**
 * 选择排序
 * @param ST
 */
void SelectSort(SSTable &ST) {
    int min_index;
    for (int i = 0; i < ST.length; ++i) {
        min_index = i;
        for (int j = i; j < ST.length; ++j) {
            if (ST.elem[min_index] > ST.elem[j]) {
                min_index = j;
            }
        }
        if (min_index != i) {
            swap(ST.elem[i], ST.elem[min_index]);
        }
    }
}

/**
 * 调整大根堆
 * TODO：调整方法还要再研究一下
 * @param ST        存放元素的动态数组
 * @param begin     需要排序的堆的起始下标
 * @param end       需要排序的堆的结束下标
 */
void AdjustDown(SSTable &ST, int begin, int end) {
    // father 表示父结点下标， length/2-1 表示最后一个父结点的下标
    // 从最后一个父结点开始往前调整
    for (int father = (end - begin + 1) / 2 - 1; father >= begin; --father) {
        int child = father * 2 + 1;  // 左孩子的下标
        if (child + 1 <= end && ST.elem[child] < ST.elem[child + 1]) {
            // 右孩子存在且大于左孩子时，用右孩子与父结点比较
            child++;
        }
        if (ST.elem[child] > ST.elem[father]) {
            swap(ST.elem[father], ST.elem[child]);
        }
    }
}

/**
 * 堆排序
 * 排列出堆中的最后一个元素，然后对n-1个元素的堆再进行一次调整，直到排完所有元素
 * @param ST
 */
void HeapSort(SSTable &ST) {
    for (int i = ST.length-1; i >= 0; --i) {
        // 先将待排序数组调整为大根堆
        AdjustDown(ST, 0, i);
        // 将根结点换到最后（最大值移动至待排序的最后一个位置）
        swap(ST.elem[0], ST.elem[i]);
    }
}

/**
 * 读取10个整型数据12 63 58 95 41 35 65  0 38 44，然后通过选择排序，堆排序，分别对该组数据进行排序，输出2次有序结果，每个数的输出占3个空格
 * @return
 */
int main() {
    SSTable ST, ST_select, ST_heap;
    ElemType A[10] = {12, 63, 58, 95, 41, 35, 65, 0, 38, 44};
    // 初始化数组
    ST_Init(ST, 10);
    ST_Init(ST_select, 10);
    ST_Init(ST_heap, 10);
    // 拷贝整型数组或浮点型数组时，用memcpy。拷贝字符串数组时，用strcpy
    memcpy(ST.elem, A, sizeof (A));             // 将数组A中的元素复制到ST.elem中
    memcpy(ST_select.elem, ST.elem, sizeof (ElemType) * ST.length);
    memcpy(ST_heap.elem, ST.elem, sizeof (ElemType) * ST.length);
    ST_Print(ST);

    // 选择排序
    SelectSort(ST_select);
    ST_Print(ST_select);

    // 堆排序
    HeapSort(ST_heap);
    ST_Print(ST_heap);

    return 0;
}